Generally, local area networks are used to connect a plurality of end-stations, e.g., computers, to each other and/or to one or more gateways which lead to wide area networks. In many cases the connections of the end-stations to each other and/or to a wide area network are very important and should not fail even for a few seconds. For example, the disconnection, even for a short period, of some Internet, banking, telephone and stock market servers may have severe economical consequences.
Local area networks generally comprise a plurality of bridging-devices (e.g., Ethernet switches, switch modules, bridges) and communication links. Each communication link connects between two or more bridging-devices or between one or more bridging-devices and one or more end-stations. Each bridging-device comprises a plurality of ports which serve as interfaces between the bridging-device and the links to which it is connected. As with other complex devices, bridging-devices and communication links may fail. Usually, the chances of a failure occurring increase with the complexity of the device.
The data passed through local area networks is generally packaged in frames (also referred to as packets), commonly having a length of up to about 1522 bytes. Many frames transmitted through local area networks are broadcast frames which are sent to most or substantially all the bridging-devices of the network. In the present application, broadcast frames refer to any frames distributed throughout a network, including frames which carry broadcast and multicast addresses and frames which carry addresses which are not recognized by the bridging-devices of the network. A commonly used broadcast scheme involves having a bridging-device, that receives a broadcast frame, forward the frame through all its ports, except the port through which the frame was received, and in some cases except ports especially defined as leading to devices not desiring to receive the frame. This broadcast scheme operates properly only if the ports and links do not form a loop in the network. If the network includes a loop of ports, a single frame may be repeatedly forwarded through the network and the network will fail. Such a situation is commonly referred to as a broadcast storm.
In many cases redundant links are added to networks, to be used in case one or more of the bridging-devices and/or links fail. A spanning tree algorithm (STA) is commonly used to block the ports leading to the redundant links and thus prevent the formation of loops. A blocking port (also referred to as a port in a blocked state, or as a blocked port) only sends and receives specific control frames (i.e., frames having the standard STA BPDU-address, as their destination address) and does not forward data frames at all. Usually, bridging-devices, which are reset or begin to operate, initially block all their ports. Then, the STA activates those ports which are to be used for forwarding data.
One common spanning tree algorithm is the 802.1D standard spanning tree algorithm (STA) which is described in “Information technology—Telecommunications and information exchange between systems—Local and metropolitan area networks—Media access control (MAC) bridges”, International Standard ISO/IEC 15802-3, 1998, ANSI/IEEE Std 802.1D, 1998 edition, the disclosure of which is incorporated herein by reference. Faster STAs are described in “Speedy Tree Protocol” and “Truncating Tree Timing”, both of which are by M. Seaman, IEEE 802.1 interim meeting, January 1999. Even these faster STAs require a few seconds to converge.
In some networks described, for example, in a white paper by Ori Bendori, titled “Lucent product support”, and available at /www.lannet.com/site/products/white/safwp-05.htm, the disclosure of which is incorporated herein by reference, redundant links are handled locally by a single bridging-device, rather than by using an STA which is a distributed algorithm and is relatively complex. The bridging-device includes active ports and blocked ports. When a failure occurs in one of the active ports, a hardware indication is provided to the bridging-device which automatically activates a predetermined one of the blocked ports, and blocks the inoperative port. Thus, the failure is overcome relatively quickly.
Some end-station devices, however, such as telephony switchboards, include only a single external port with which they connect to a local area network. In order to ensure continuous connection of the end-station to the network, the end-station is connected to a plurality of bridging-devices through an Ethernet repeater, under the assumption that simple repeaters fail much more rarely than bridging-devices, which are relatively complex. In such a configuration it is not possible to use the method described in the Ori Bendori paper, as a single port connects the end-station to the bridging-devices. Therefore, the blocking must be performed by the plurality of bridging-devices cooperatively and not by a single device. In other cases it may be desired that the blocking be performed by the bridging-devices even when the end-station has more than one port. For example, in some cases it is not practical to change the end-station devices to operate in accordance with special, fast, port blocking methods.
In some cases a failure of a device or link may be partial, for example, a link may operate only in one direction and not in the other direction. Existing blocking methods do not always detect such partial failures. There are links which perform hardware tests in both directions before reporting that the link is operative. These hardware tests, however, do not catch all the possible problems which could cause the connection between two devices to be inoperative. Thus, in some cases messages are not properly transmitted from one bridging-device to the other although the hardware indicates the link is operative. Using the indications of the hardware may result in wrong operation of the STA in activating a port which should be blocked, which may cause a broadcast storm, or in blocking a port which should be active which results in a network disconnection.
A trivial solution involves sending hello messages between two bridging-devices of a network connected by a link, and determining the operability of the link based on whether the hello messages are received. This solution can be used on a link connecting only the two bridging-devices which transmit the hello messages or on a link connecting additional devices, for example, on a link connecting two bridging-devices and an end-station. The determination of the operability of the link may be performed based solely on the reception of the hello messages or based on a combination of the reception of the hello messages and on hardware indications. According to the operability determination the bridging-devices decide whether to block or activate their port to the link. This solution, however, has a few drawbacks. For example, if both the bridging-devices do not receive hello messages from each other due to a fault in the link, and the hardware does not detect the fault, both the bridging-devices may assume the other bridging-device is faulty and activate their ports. When the fault disappears a loop is formed and the network may suffer from a broadcast storm.
A broadcast storm may also result if a link operates only in one direction and the problem is not identified by the hardware.
Generally, STAs and other port blocking schemes define a primary topology which is active when the devices of the network are operative. When a failure occurs, the network reverts to a backup topology. When the failure is overcome, the network returns to the primary topology. This, however, causes an extra, unnecessary, switch of the network which interrupts the data flow in the network.